package a09_贪心算法;

/**
 * <p>
 * a22_单调递增的数字复习2
 * </p>
 *
 * @author flyduck
 * @since 2025/5/6
 */
public class a22_单调递增的数字复习2 {
    public static void main(String[] args) {
        System.out.println(monotoneIncreasingDigits(1000));
    }
    //10
    //9

    //1234
    //1234

    //332
    //299

    //332
    // 22
    // 29

    //思路：如果发现两位不符合要求，对前一位做减减的处理，这样才能让后一位有大于前一位的可能
    //后一位要取最大的值即9

    //注意1：从前往后还是从后往前
    //从前往后：332，解出来是329，然后又得调整第一位
    //从后往前：332，解出来是329，再往前，就变成了299

    //注意2：不是减1，而是减减

    //注意3：1000
    //0900
    //所以不能每次遍历就去赋值，而去记录
    public static int monotoneIncreasingDigits(int n) {
        String str = String.valueOf(n);
        char[] chars = str.toCharArray();

        int flag = chars.length;
        for (int i = chars.length - 2; i >= 0; i--) {
            if(chars[i] > chars[i+1]){
                chars[i] = (char)(Character.getNumericValue(chars[i]) - 1 + '0');
                flag = i+1;
            }
        }
        for (int i = flag; i < chars.length; i++) {
            chars[i] = '9';
        }
        return Integer.valueOf(new String(chars));
    }
}
